package com.leet;

import java.util.*;

public class Connect {

    //结果
    List<String> ans = new ArrayList<>();

    Boolean isStackable(StringBuilder s1){
        if(s1.length()==0){
            return true;
        }
        String s = s1.toString();
        char[] chars = s.toCharArray();
        List<Character> stack = new ArrayList<>();
        for (char aChar : chars) {
            if(stack.isEmpty()){
                stack.add(aChar);
            }
            if (aChar == '(') {
                    stack.add(aChar);
            }
            if (aChar == ')') {
                if (stack.get(stack.size() - 1) == '(') {
                    stack.remove(stack.size() - 1);
                } else {
                    stack.add(aChar);
                }
            }
        }
        return stack.isEmpty();
    }

    void backTracking(int n,StringBuilder tmp){
        if(tmp.length()==2*n){
            ans.add(new StringBuilder(tmp).toString());
            return;
        }
        char[] pattern = "()".toCharArray();
        for(int i = 0; i < 2; i++){
            if(isStackable(tmp)){
                tmp.append(pattern[i]);
                backTracking(n,tmp);
                tmp.deleteCharAt(tmp.length()-1);
            }
        }

    }
    public List<String> generateParenthesis(int n) {
        ans.clear();
        StringBuilder tmp = new StringBuilder();
        backTracking(n,tmp);
        return ans;
    }
}
